#include <dbg.h>

using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        int fresh = 0;
        vector<pair<int, int>> q;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ++fresh;  // 统计新鲜橘子
                } else if (grid[i][j] == 2) {
                    q.emplace_back(i, j);  // 统计腐烂橘子
                }
            }
        }
        dbg(fresh, q);

        int res = 0;
        while (fresh > 0 &&
               !q.empty()) {  // 只要有新鲜橘子，且有腐烂橘子，就继续
            ++res;            // 开始腐烂
            vector<pair<int, int>> next;
#ifdef without_auto
            for (pair<int, int>& p : q) {  // 如果显示声明 pair<int, int>& p
                int x;
                int y;
                tie(x, y) = p;  // 需要使用 tie 来将 pair 拆分成 x 和 y
#endif
                for (auto& [x, y] : q) {
                    for (const vector<int>& d : directions) {
                        int i = x + d[0];
                        int j = y + d[1];
                        if (i >= 0 && i < m && j >= 0 && j < n &&
                            grid[i][j] == 1) {  // 上下左右 新鲜橘子
                            grid[i][j] = 2;
                            next.emplace_back(i, j);
                            --fresh;
                        }
                    }
                }
                q = next;  // 下一轮
                dbg(fresh, q);
            }
            return fresh == 0 ? res : -1;  // 只有新鲜橘子返回 -1
        }

    private:
        const vector<vector<int>> directions{{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    };

    int main() {
        Solution s;

        vector<vector<int>> grid{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}};

        dbg(s.orangesRotting(grid));

        return 0;
    }